给定一棵二叉树，采用广度优先搜索(BFS) 算法，返回右视图所有节点的值。其中右视图定义为：二叉树的右视图是从树的右侧看过去时可见的节点集合，即右视图中的每个节点都是某一层中最右侧的节点。

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def rightSideView(root):
    rightmost_value_at_depth = {}
    max_depth = -1

    node_queue = []
    depth_queue = []
    node_queue.append(root)
    depth_queue.append(0)

    while node_queue:
        node = node_queue.pop(0)
        depth = depth_queue.pop(0)

        if node is not None:
            max_depth = max(max_depth, depth)
            rightmost_value_at_depth[depth] = node.val

            node_queue.append(node.left)
            node_queue.append(node.right)

            # (1) 填空处
            depth_queue.append(depth + 1)
            depth_queue.append(depth + 1)

    right_view = []
    # (2) 填空处
    for depth in range(max_depth + 1):
        right_view.append(rightmost_value_at_depth[depth])

    return right_view

if __name__ == "__main__":
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.right = TreeNode(5)
    root.right.right = TreeNode(4)

    print(rightSideView(root))

游乐园的过山车每次限坐4 人，用循环队列管理排队（容量MAX=5，空一格判满）。下面代码执行后，循环队列是否已满？rear 的值是多少？

MAX = 5
queue = [None] * MAX
front = 0
rear = 0

def enqueue(x):
    global rear, queue
    queue[rear] = x
    rear = (rear + 1) % MAX

def dequeue():
    global front
    front = (front + 1) % MAX

if __name__ == "__main__":
    enqueue(1)
    enqueue(2)
    enqueue(3)
    enqueue(4)

    dequeue()
    dequeue()

    enqueue(5)
    enqueue(6)

    print("队列数组: ", queue)
    print("front下标位置: ", front)
    print("rear下标位置: ", rear)

在二叉搜索树（BST）中，若中序遍历的序列为{1, 2, 3, 4, 5}，且先序遍历的第一个序列元素为3，则下列说法正确的是（）。

下列关于树的遍历的说法中，正确的一项是（）。

在以下计算机系统应用场景中，最适合使用循环队列的是（）。

下面的代码在主程序if name == " main ": 中有没有一行会导致运行错误，如果有请找出错误行（）

class Pet:
    def __init__(self, n, a):
        self._name = n
        self._age = a
    def get_name(self):
        return self._name
    def birthday(self):
        self._age += 1

if __name__ == "__main__":
    cat = Pet("奶茶", 2)
    print(cat.get_name())       # ①
    cat.birthday()              # ②
    cat._name = "大橘"          # ③
    print(cat.get_name())       # ④

关于格雷编码（Gray Code），下列说法正确的是（）。

对n个不同符号的符号进行哈夫曼编码。若生成的哈夫曼树共有115个结点，则n的值是（）。

下列代码中，s1 .draw() 和s2 .draw() 能正确运行并输出不同结果的主要原因是（）。

class Shape:
    def draw(self):
        print("绘制图形")

class Circle(Shape):
    def draw(self):
        print("绘制圆形")

class Rectangle(Shape):
    def draw(self):
        print("绘制矩形")

if __name__ == "__main__":
    s1 = Circle()
    s2 = Rectangle()

    s1.draw()
    s2.draw()

小朋友们去邻里拜年，每个家里有不同数量的糖果。规则是：不能连续进入两个相邻的房子（即不能同时取相邻两家的糖果）。目标是拿到最多糖果。以下是代码实现，请补全横线。

def visit(nums):
    if not nums:
        return 0

    size = len(nums)
    if size == 1:
        return nums[0]

    dp = [0] * size
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])

    for i in range(2, size):
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])  # 填空处

    return dp[size - 1]

if __name__ == "__main__":
    nums1 = [1, 2, 3, 1]
    print(visit(nums1))

    nums2 = [2, 7, 9, 3, 1]
    print(visit(nums2))

    nums3 = [5]
    print(visit(nums3))

    nums4 = []
    print(visit(nums4))

某二叉树共有10个结点，记为A~J，已知它的先序遍历序列为：<strong>AB D H I E C F J G</strong>，中序遍历序列为：<strong>H DI B E A FJ C G</strong>，则该二叉树的后序遍历序列是（）。

以下关于Python 类继承的代码，执行后输出结果是？（）

class Animal:
    def __init__(self, name):
        self.name = name

    def speak(self):
        return "动物叫声"

class Dog(Animal):
    def speak(self):
        return f"{self.name}: 汪汪汪"

class Cat(Animal):
    def __init__(self, name, color):
        super().__init__(name)  # 调用父类构造方法
        self.color = color

    def speak(self):
        return f"{self.name} ({self.color}): 喵喵喵"

dog = Dog("旺财")
cat = Cat("咪宝", "橘色")
print(dog.speak(), cat.speak())

下列关于树的深度优先搜索（DFS）的说法中，正确的是（）。

元宵节晚上，小朋友沿着一条发光石板路前进，每次可以向前走1 块或2 块石板。若dp[i] = dp[i - 1]+ dp[i - 2]，下面关于dp[i] 的含义最合适的是（）。

有6 个字符，它们出现的次数分别为：{2 , 3 , 3 , 4 , 6 , 8 }，现在用哈夫曼编码为这些字符编码，最小加权路径长度WPL（每个字符的出现次数X它的编码长度，再把每个字符结果加起来）的值为（）。

设二叉树共有n个结点，函数 preorderTraversal 的时间复杂度为O(n)，空间复杂度为O(n)。

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def preorder(root, res):
    if root is None:
        return
    res.append(root.val)
    preorder(root.left, res)
    preorder(root.right, res)

def preorderTraversal(root):
    res = []
    preorder(root, res)
    return res

if __name__ == "__main__":
    root = TreeNode(1)
    root.right = TreeNode(2)
    root.right.left = TreeNode(3)
    result = preorderTraversal(root)
    print("前序遍历结果: ", result)

Python 中的继承支持单继承和多继承，但子类无法直接访问父类的私有成员。

在Python 中使用列表存储按层序遍历的完全二叉树时，若根节点存储在tree[0]，则对于任意非空节点 tree[i]，其右孩子（如果存在）必然位于tree[2 * i + 2]。

以下代码实现了0 -1背包问题的一维动态规划解法，内层循环采用经典的逆序遍历方式。若将内层循环改为正序遍历（即for j in range(w[i], W + 1):），仍能得到正确答案。

def knapsack_01():
    W = 5
    w = [2, 3, 4]
    v = [10, 1, 1]
    n = 3
    dp = [0] * (W + 1)

    for i in range(n):
        for j in range(W, w[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - w[i]] + v[i])

    print(dp[W])

knapsack_01()

对如下结构的树，执行travel 函数，输出结果是1 2 3 4 5。

class Node:
    def __init__(self, v):
        self.val = v
        self.left = None
        self.right = None

def travel(root):
    if not root:
        return
    stack = []
    stack.append(root)
    while stack:
        cur = stack.pop()
        print(cur.val, end=" ")
        if cur.right:
            stack.append(cur.right)
        if cur.left:
            stack.append(cur.left)

if __name__ == "__main__":
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)
    travel(root)

下面定义了一个表示二维坐标点的类Point，并提供了一个带参数的构造函数，但第②行Point b ; 会调用编译器自动生成的默认构造函数，将b .x 和b .y 被初始化为0.0，程序可以正常编译运行。

class Point:
    def __init__(self, px, py):
        self.x = px
        self.y = py

    def print(self):
        print(f"({self.x}, {self.y})")

if __name__ == "__main__":
    a = Point(3.0, 4.0)  # ①
    # ②
    b = Point(0, 0)
    a.print()

若所有字符出现频率相同，则哈夫曼编码一定会得到完全二叉树。

哈夫曼编码是一种变长的前缀编码，在解码时不需要额外的分隔符就能唯一还原，这是因为在哈夫曼树中，任何一个字符的叶子结点都不会成为另一个字符结点的祖先。

在Python 中使用列表模拟栈来非递归地实现二叉树的前序遍历，为了保证遍历顺序正确，在处理完当前结点后，应该先将该结点的左孩子压入栈中，然后再将右孩子压入栈中。（）

在动态规划问题中，状态空间相同且没有重复计算的情况下，“状态转移方程+递推”与“递归+记忆化搜索”的时间复杂度通常相同。

选数

完全二叉树